package cn.nju.sirx.algorithm.sort;

/**
 * Quick sort.
 * 
 * @author SirX
 */
public class QuickSort implements ISort {

    @Override
    public <T extends Comparable<? super T>> void sort(T[] data) {
        sort(data, 0, data.length - 1);
    }

    private <T extends Comparable<? super T>> void sort(T[] data, int i, int j) {
        if (i >= j)
            return;

        int begin = i, end = j;
        T tmp = data[i];
        boolean toLeft = true;
        while (i != j) {
            if (toLeft) {
                if (data[j].compareTo(tmp) < 0) {
                    data[i++] = data[j];
                    toLeft = false;
                } else {
                    j--;
                }
            } else {
                if (data[i].compareTo(tmp) > 0) {
                    data[j--] = data[i];
                    toLeft = true;
                } else {
                    i++;
                }
            }
        }
        data[i] = tmp;
        sort(data, begin, i - 1);
        sort(data, i + 1, end);
    }

}
